package com.taldh.algorithm.动态规划;

import org.junit.Assert;
import org.junit.Test;

public class ClimbStairs {

    public int climbStairs(int n) {
        //动态规划法
        //寻找最优子结构
        //第 i 阶可以由以下两种方法得到：
        //
        //在第 (i-1) 阶后向上爬一阶。
        //
        //在第 (i-2) 阶后向上爬 22 阶。
        //
        //所以到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和。
        //
        //令 dp[i] 表示能到达第 i 阶的方法总数：
        //
        //dp[i]=dp[i-1]+dp[i-2]
        //
        if (n == 1) {
            return 1;
        }

        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i-1] + dp[i - 2];
        }
        return dp[n];

        //自底向上，类似斐波那契算法
//        if (n < 1) {
//            return 0;
//        }
//        if (n < 2) {
//            return 1;
//        }
//        if (n < 3) {
//            return 2;
//        }
//        int i = 1;
//        int j = 2;
//        int fn = 0;
//        for (int k = 3; k < n + 1; k++) {
//            fn = i + j;
//            if (k % 2 == 1) {
//                i = fn;
//            } else {
//                j = fn;
//            }
//        }
//        return fn;
    }
    @Test
    public void test() {
        Assert.assertEquals(3, climbStairs(3));
    }
}